
/**
 * https://leetcode-cn.com/problems/min-stack/
 * 最小栈
 */
class MinStack {
    private arr: number[]
    private min: number;
    constructor() {
        this.arr = []
        // 初始为最大值
        this.min = Number.MAX_SAFE_INTEGER
    }

    push(val: number): void {
        // 小于min, 放入val
        const min = this.min
        if (val <= min) {
            // 先放入原来比较小的, 保证在弹出最后一个的时候能找到最小值
            this.arr.push(min);
            // 更新min
            this.min = val
        }
        // 将当前值放入栈中
        this.arr.push(val)
    }

    pop(): void {
        // 弹出最后一个
        const v = this.arr.pop()!;
        // 最后一个就是最小值
        if (v === this.min) {
            this.min = this.arr.pop()!
        }

    }

    top(): number {
        const len = this.arr.length;
        return this.arr[len - 1];
    }

    getMin(): number {
        return this.min
    }
}



class MinStack3 {
    private arr: number[]
    private minStack: number[]
    constructor() {
        this.arr = []
        this.minStack = [Infinity]
    }

    push(val: number): void {
        // 放入arr
        this.arr.push(val);
        const stack = this.minStack
        const len = stack.length;

        // 和栈顶比较大小, 放入比较小的
        stack.push(Math.min(val, stack[len - 1]))


    }

    pop(): void {
        // 弹出最后一个
        this.arr.pop();
        this.minStack.pop()

    }

    top(): number {
        const len = this.arr.length;
        return this.arr[len - 1];
    }

    getMin(): number {
        const len = this.minStack.length;
        return this.minStack[len - 1]
    }
}


class MinStack2 {
    private arr: number[]
    private minStack: number[]
    constructor() {
        this.arr = []
        this.minStack = []
    }

    push(val: number): void {
        // 放入arr
        this.arr.push(val);

        // 在minStack中找到比val大的第一个数
        const i = this.minStack.findIndex(item => item < val)
        if (i == -1 || i == undefined) {
            // 找不到比val大, 往尾部部插入
            this.minStack.push(val)
        } else {
            // 往i位置添加val
            this.minStack.splice(i - 1, 0, val)
        }

    }

    pop(): void {
        // 弹出最后一个
        const val = this.arr.pop();
        console.log(val)
        // 从minStack中找到val并将其删掉
        const i = this.minStack.findIndex(item => item === val)!
        this.minStack.splice(i, 1);
    }

    top(): number {
        const len = this.arr.length;
        return this.arr[len - 1];
    }

    getMin(): number {
        const len = this.minStack.length;
        return this.minStack[len - 1]
    }
}
